package com.tiny.work;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  public static void main(String[] args) throws IOException {

    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    String sc = br.readLine();
    int city, flight;
    String[] split = sc.split(" ");
    city = Integer.parseInt(split[0]);
    flight = Integer.parseInt(split[1]);
    int[][] graph = new int[city][city];

    for (int i = 0; i < city; i++) {
      for (int j = 0; j < city; j++) {
        graph[i][j] = 100000007;
      }
    }
    for (int i = 0; i < city; i++) {
      graph[i][i] = 0;
    }
    int row = 0, line = 0;
    while ((sc = br.readLine()) != null && (!sc.equals(""))) {
      split = sc.split(" ");
      row = Integer.parseInt(split[0]);
      line = Integer.parseInt(split[1]);
      graph[row - 1][line - 1] = Integer.parseInt(split[2]);
      graph[line - 1][row - 1] = Integer.parseInt(split[2]);
    }
    int i, j, k;
    for (k = 0; k < city; k++) {
      for (i = 0; i < city; i++) {
        for (j = 0; j < city; j++) {
          if (graph[i][k] + graph[k][j] < graph[i][j]) {
            graph[i][j] = graph[i][k] + graph[k][j];
          }
        }
      }
    }

    int result = 0;
    for (i = 0; i < city; i++) {
      for (j = 0; j < city; j++) {
        result = Math.max(result, graph[i][j]);
      }
    }
    System.out.print(result);
  }
}
